package com.my.sorting_algorithm;


import java.util.Arrays;

public class SortAlgorithm {


    public static void main(String[] args) {


        SortAlgorithm sortAlgorithm = new SortAlgorithm();

        int [] input = {6,1,2,7,9,3,4,5,10,8};
        int [] input2 = {5,4,7,8,6,1};
        //System.out.println(sortAlgorithm.quickSort( 0, input.length - 1,input));
        System.out.println(sortAlgorithm.quickSort(input));
        //System.out.println(Arrays.toString(sortAlgorithm.headSort(input2)));
    }

    public int [] quickSort(int [] input){

        if(input == null || input.length <=1){
            return input;
        }
        //quickSort(input, 0, input.length - 1);
        quickSort( 0, input.length - 1, input);
        for(int i = 0;i < input.length;i++){
            System.out.print(input[i] + "    ");
        }
        System.out.println();
        return input;

    }

    public static void quickSort(int start, int end, int[]nums){

        if(start > end)
            return ;
        System.out.println("start=====" + start + " end=====" + end);
        int pivot = nums[start];
        int startTmp = start;
        int endTmp = end;
        while(startTmp < endTmp){
            while(startTmp < endTmp && nums[endTmp] >= pivot){
                endTmp--;
            }
            nums[startTmp] = nums[endTmp];

            while(startTmp < endTmp && nums[startTmp] < pivot){
                startTmp++;
            }
            nums[endTmp]= nums[startTmp];

        }
        nums[startTmp] = pivot;
        quickSort(start, startTmp-1, nums);
        quickSort(startTmp+1, end, nums);
    }

    /**
     * 快速排序
     *
     * @desc 双指针 多趟排序
     *
     *
     * @param input
     * @param start
     * @param end
     */
    public void quickSort(int [] input, int start, int end){
        if(start > end){
            return ;
        }
        //System.out.println("-=------------start is: " + start + "    end is: " + end);
        int viot = input[start];
        int i = start, j = end;
        while (i < j){
            while(j > i &&input[j] >= viot){
                j--;
            }
            input[i] = input[j];
            while (i < j && input[i] < viot){
                i++;
            }
            input[j] = input[i];
        }
        input[i] = viot;
        quickSort(input, start, i-1);
        //System.out.println("----------------" + i + "    j: ===" + j);
        quickSort(input, i + 1, end);
    }


    /**
     * @author zlx
     * @Description 堆排序
     * @Date 3/31/21
     * @Param [nums]
     * @return int[]
     **/
    public int[] headSort(int [] nums){

        int len = nums.length;

        //初始化堆，构建一个最大堆
        for(int i = len/2 - 1;i >=0;i--){
            headAdjust(nums, i, len);
        }

        //将堆定的元素和最后一个元素交换，并重新调整堆
        for(int i = len - 1;i > 0;i--){

            int tmp = nums[i];
            nums[i] = nums[0];
            nums[0] = tmp;
            headAdjust(nums, 0, i);
        }
        return nums;
    }

    private void headAdjust(int[] nums, int index, int len) {
        //保存当前节点下标
        int max = index;
        //当前节点左下标
        int lchild = 2 * index;
        //当前节点右下标
        int rchild = 2 * index + 1;
        if(lchild < len && nums[lchild] > nums[max]){
            max = lchild;
        }
        if(rchild < len && nums[rchild] > nums[max]){
            max = rchild;
        }
        if(max != index){
            int tmp = nums[index];
            nums[index] = nums[max];
            nums[max] = tmp;
            headAdjust(nums, max, len);
        }
    }
}
